package com.example.hot100;

import java.util.Arrays;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *  如果数组中不存在目标值 target，返回 [-1, -1]。
 *
 *  进阶：
 *  你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 *
 *  示例 1：
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 *
 *  示例 2：
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 *
 *  示例 3：
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 */
public class Leetcode34_SearchRange {
    public static void main(String[] args) {
        int target = 6;
        int[] nums = {5, 7, 7, 8, 8, 10};

        target = 1;
        nums = new int[] {1};
        System.out.println(Arrays.toString(new Solution().searchRange(nums, target)));
    }

    static class Solution {
        /**
         * 二分法
         * @param nums
         * @param target
         * @return
         */
        private int[] searchRange2(int[] nums, int target) {
            int start = binarySearch(nums, target, true); // 寻找第一个大于等于target的下标
            int end = binarySearch(nums, target, false) - 1; // 寻找最后一个等于target的下标

            if (start <= end && end < nums.length && nums[start] == target && nums[end] == target) {
                return new int[] {start, end};
            }
            return new int[] { -1, -1};
        }

        /**
         * 寻找第一个大于等于 target 的下标
         *
         * @param nums
         * @param isContainEqual 是否包含等于
         * @return
         */
        private int binarySearch(int[] nums, int target, boolean isContainEqual) {
            int left = 0, right = nums.length - 1, res = nums.length;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (nums[mid] > target || (isContainEqual && nums[mid] >= target)) {
                    right = mid - 1;
                    res = mid;
                } else {
                    left = mid + 1;
                }
            }
            return res;
        }

        private int[] searchRange1(int[] nums, int target) {
            int[] range = new int[2];
            if (nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target)
                return new int[]{-1, -1};

            int i = 0;
            while (i < nums.length) {
                if (nums[i] != target) ++i;
                else break;
            }

            if (i <= nums.length - 1) {
                range[0] = i;
                while (i < nums.length) {
                    if (nums[i] == target) ++i;
                    else break;
                }
                range[1] = i - 1;
                return range;
            } else {
                return new int[] {-1, -1};
            }
        }

        public int[] searchRange(int[] nums, int target) {
            return searchRange2(nums, target);
        }
    }
}
